1. Field of the Invention
This invention relates to computer networks and more specifically to classifying packets transferred over a computer network.
2. Background Information
A computer network is a geographically distributed collection of interconnected network links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). End nodes, such as personal computers or workstations, typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate node, such as a switch or router, having a plurality of ports, which may be coupled to the networks. For example, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs at high speed. The switching function includes receiving a data packet that originated from a source node at a source port and transferring that packet to at least one destination port for forwarding to a destination node.
A router may also be used to interconnect LANs executing different LAN standards and/or to provide higher level functionality than a switch. If the LAN standards associated with the source and destination nodes are dissimilar (e.g., Ethernet and token ring), the router may also alter the format of the packet so that it may be received by the destination node. Routers typically operate at the network layer of a communications protocol stack used by the network, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISPs equipment. Here, a router may be utilized to interconnect a plurality of private networks to an IP backbone network.
Typically, high-speed input links of the private networks couple to input ports of the router that feed to a single output buffer connected to a shared output link coupled to the IP backbone network. The router may function to aggregate different kinds of packet traffic (e.g., high-priority packet traffic versus lower-priority packet traffic) over the shared output link and different qualities of service (QoS) may also be required for packets transferred over the shared link. For example, packets containing voice information (voice packets) may require a higher quality of service than packets that simply contain data information, such as data contained in a file.
One way to implement QoS is to enable packets to be classified such that certain packets, e.g., voice packets, are guaranteed an established level of service. One prior technique for classifying packets in this manner involves classification rules and content-addressable memory (CAM) hardware. According to this technique a set of classification rules are defined and the CAMs are configured to implement the rules. A packet is classified by applying various content contained in a packet to the CAM. The output of the CAM, e.g., an address, is then used to make a QoS decision, which might include placing the packet on a particular calendar queue for transfer at a specific time.
One problem with the above-described technique, however, is that it tends not to scale well as the CAM typically must contain at least 2n entries of n size where n is the size in bits of the packet's content that is applied to the CAM. Thus for example, if classification is based on a single 8-bit field within the packet, the CAM must contain at least 256 8-bit entries. Likewise, if the classification is based on three 8-bit fields contained within the packet, the CAM must contain at least 16,777,216 24-bit entries; thus forcing the CAM to have a capacity that is capable of holding at least 50,331,648 bytes of information. Conventional CAMs with such capacity are either not readily available or prohibitively expensive.